In modern computer systems, a First-In-First-Out (FIFO) buffer may be needed between two devices that are functioning independently or that have different data transfer rates. Control hardware must be designed to control the items of data or instructions stored in the FIFO queues. In a FIFO queue, items enter an input port and move sequentially through the queue of item registers to an output port. FIFO queues typically hold instructions, data, addresses or transactions, which are referred to collectively as "items." As items are added to the queue, control logic is required to keep track of where each item is stored and its order relative to other items. When new items are added to a queue they are placed at the back of the queue. Items are then moved forward toward the front of the queue in a process called advancing the queue. When an item reaches the front of the queue, it becomes eligible to be serviced.
Servicing an item may entail, for example, moving the item to another part of the system, decoding the item or any number of other defined actions. Once an item is serviced, it is no longer needed and can safely be discarded. Once an item has been serviced and discarded, the entire queue advances such that each item in the queue moves one step closer to the front of the queue. Sometimes items are deleted from a queue before they reach the front; this is referred to as "queue deletion." Queue deletion generally results in a "bubble" in the queue. A bubble is an invalid item that must not be serviced surrounded by valid items that must be serviced.
Modern computer systems require specialized hardware to perform queue management control functions. FIG. 1 shows a block diagram of a queue management controller 100. The queue management controller 100 is comprised of a plurality of item registers 102.sub.1-n nconnected in series and a plurality of valid bit registers 104.sub.1 -104.sub.n connected in series. Each item register 102.sub.1 -102.sub.n has a corresponding valid bit register 104.sub.1 -104.sub.n. The output of the item register 102.sub.n and the output of the front valid bit register 104.sub.n are both connected to the servicing logic means 106 of the queue controller. The valid bit corresponding to each item register identifies whether an item is to be serviced. In the embodiment shown in FIG. 1, the valid bit registers 104.sub.1 -104.sub.n is set to one to identify an item that needs servicing. The valid bit register 104.sub.1 -104.sub.n is cleared to identify an item that should not be serviced (a queue deletion.)
In operation, items are loaded into the first item register 102, and then as the registers are clocked, the items advance through the queue of registers until the item reaches the "front" register 102.sub.n where it can be serviced and/or discarded. When an item to be serviced (Valid bit=1) reaches the "front" register, the item is serviced and then discarded. When an item that is not to be serviced reaches the front register, it is discarded after a brief delay when it is examined.
The primary disadvantage of the queue management controller shown in FIG. 1 is the delay from the time an item is inserted into item register 102 until it reaches item register 102.sub.n where it can be examined and serviced. This delay is typically equal to one cycle for each of the n item registers and therefore can be very severe. There is also an obvious disadvantage to this method of handling queue deletions-by allowing the bubble to advance to the front of the queue, a cycle is lost examining and discarding it that could otherwise be spent servicing the next valid item.
In an alternative queue management control system, queue deletions may be handled by the queue management controller by selectively clocking the portion of the queue from the deleted item backwards to eliminate the bubble. However, this technique only eliminates the one cycle delay which is lost when the bubble advances to the front of the queue and does not eliminate the delay from the time the item is inserted into the register 102.sub.1 until it reaches item register 102.sub.n. Compared to the clocking shown in FIG. 1 where the clocks on all the registers are tied together, selective clocking increases the complexity of the circuitry supporting the clocking function.
FIG. 2 shows a block diagram of an alternative prior art queue management controller 200. The queue management controller 200 includes a plurality of item registers 202.sub.1 -202.sub.n and a counter control logic means. The counter control logic means includes: a back pointer logic block 206, a front pointer logic block 208 and a valid item counter 210. The counter control logic means 204 and the item registers 202.sub.1 -202.sub.n are connected to a servicing logic means 214.
In contrast to the queue management controller 100 shown in FIG. 1 which uses valid bits to determine if an item is to be serviced, the queue management controller 200 uses counter logic to determine whether an item is to be serviced. Special pointer registers indicate which registers are the front and back of the queue. A count of the items in the queue is maintained by the valid item counter 210. As long as the count of the valid item counter 210 is greater than zero, servicing of items at the front of the queue continues.
In contrast to the queue management controller 100 shown in FIG. 1, the item registers of the queue management controller 200 can be accessed individually. To insert an item into the queue, the item is loaded into the register indicated by the back pointer register. After the item is loaded, the back pointer register incremented to point to the next register. The front pointer register points to the register currently being serviced. When the item in the front pointer register has been serviced, this pointer register value is incremented to point to the next item to be serviced. If the value of either the front pointer register or the back pointer register is greater than the value of the highest register number after being incremented, the value of that pointer register is set to zero (wraparound condition).
Compared to the queue management controller 100 shown in FIG. 1, the queue management controller 200 eliminates the long servicing delay for the first item to be inserted into a queue and is a good choice for many queues. However, the queue management controller 200, does not handle queue deletions well. Valid bit registers may be added for each of the corresponding item registers so that queue deletions can be allowed, however, eliminating the bubbles that result from queue deletions is difficult. For queues that experience a significant number of queue deletions, a high percentage of bubbles implies very inefficient use of queue registers.
In a competitive business environment, computer systems must provide the highest level of performance with a minimum of circuitry complexity. The queue management controller shown in FIG. 1, handles bubbles and queue deletions well, it is at the cost of processor delay. The queue management controller shown in FIG. 2, is flexible in that items may be loaded anywhere in the queue, however, the queue management controller does not deal well with queue deletions. An improved method and apparatus for management of queues having deleteable entries which minimizes bubble formation and processor delay is needed.